Section: New Results

Managing the system (via probabilistic modeling)

Belief propagation inference for traffic prediction

Participants : Cyril Furtlehner, Jean-Marc Lasgouttes, Arnaud Lewden, Victorin Martin.

This work [41] deals with real-time prediction of traffic conditions in a setting where the only available information is floating car data (FCD) sent by probe vehicles. The main focus is on finding a good way to encode some coarse information (typically whether traffic on a segment is fluid or congested), and to decode it in the form of real-time traffic reconstruction and prediction. Our approach relies in particular on the belief propagation algorithm.

These studies are done in particular in the framework of the projects TRAVESTI and Pumas.

This year's highlights are

• A particular effort has been done this year in studying the theoretical aspects of the ways to encode real valued variable into an binary Ising model. A publication on the subject is in preparation.

• A review of our work on road traffic inference using methods from statistical physics has been published [21] .

• The investigation of the effect of various types of normalization in the belief propagation algorithm has lead to a technical report [38] .

• Arnaud Lewden has specified and implemented the new software BPstruction, which is our contribution to the Pumas project. Besides implementing traffic reconstruction from FCD, it is intended as a testbench for our research on inference using Belief Propagation.

• Victorin Martin has given a talk at the “Séminaire de Modélisation des Réseaux de Transport” at IFSTTAR. He presented there our method for real-time traffic reconstruction and prediction.

• Jean-Marc Lasgouttes also presented this work at the Xerox Research Centre Europe seminar.

Evaluation of dual mode transport system by event-driven simulation

Participants : Arnaud de La Fortelle, Sami Mahari.

The European project CATS — City Alternative Transport System — is developing and evaluating a new vehicle system using a single type of vehicle for two different usages: individual use or collective transport. Real experiments will necessarily take place with a limited number of vehicles and stations. Hence there is a need for evaluation using simulations. We have been developing a discrete events simulator for that purpose, based on a previous work done for collective taxis  [42] .

Our model relies on an adapted events/decision graph that extends previous graphs. The new feature of this model is the way we deal with two modes that can be extended to many other modes. This work therefore shows on a concrete example a method to efficiently merge multiple modes into one model.

• This year has seen the design and first implementation of the simulator.

• The results have been presented at a conference [29] .

Multi-speed exclusion processes

Participants : Cyril Furtlehner, Jean-Marc Lasgouttes, Maxim Samsonov.

The slow-to-start mechanism is known to play an important role in the particular shape of the Fundamental diagram of traffic and to be associated to hysteresis effects of traffic flow. We study this question in the context of stochastic processes, namely exclusion and queueing processes, by including explicitly an asymmetry between deceleration and acceleration in their formulation. Spatial condensation phenomena and metastability are observed, depending on the level of the aforementioned asymmetry. The relationship between these 2 families of models is analyzed on the ring geometry, to yield a large deviation formulation of the fundamental diagram (FD)

This work has been presented at the TGF'11 conference [22] , and a more extensive article is in preparation for a journal.

Dynamics of points of interest in a social game

Participants : Guy Fayolle, Jean-Marc Lasgouttes.

Ma Micro Planète is a geolocalized video game which entices players to use sustainable means of transport. At the heart of the game are community-driven points of interest (POI's), or sites, which have a score that depends on the players activity. The aim of this work is to understand the dynamics of the underlying stochastic process.

We examine the system in the thermodynamic limit, as the number of players tends to infinity, the existence of which is proved under general conditions, where the probability of increasing the score of a visited POI is a function of the state of the system. Concerning the existence of a stationary regime, some complete answers are given for particular values of the parameters, and the existence of possible phase transition phenomena is enlightened.

A publication on the subject is in preparation.

Random walks in the quarter plane

Participant : Guy Fayolle.

In collaboration with K. Raschel (CNRS, Université F. Rabelais à Tours), we pursued the works initiated in 2010 in two main directions.

The zero drift case

In several recent studies on random walks with small jumps in the quarter plane, it has been noticed that the so-called group of the walk governs the behavior of a number of quantities, in particular through its order. In the article [11] , when the drift of the random walk is equal to 0, we provide an effective criterion giving the order of this group. More generally, we also show that in all cases where the genus of the algebraic curve defined by the kernel is 0, the group is infinite, except precisely for the zero drift case, where finiteness is quite possible.

Counting and asymptotics

The enumeration of planar lattice walks, is a classical topic in combinatorics. For a given set $𝒮$ of allowed unit jumps (or steps), it is a matter of counting the number of paths starting from some point and ending at some arbitrary point in a given time, and possibly restricted to some regions of the plane.

Like in the probabilistic context, a common way of attacking these problems relies on the following analytic approach. Let $f(i,j,k)$ denote the number of paths in ${\mathbb{Z}}_{+}^2$ starting from $(0,0)$ and ending at $(i,j)$ at time $k$. Then the corresponding CGF

satisfies the functional equation

where $x,y,z$ are complex variables, although the time variable $z$ plays somehow the role of a parameter. The question of the type of the associated counting generating functions, that is rational, algebraic, holonomic (solution of a linear differential equation with polynomial coefficients), was solved whenever the group is finite (see RA 2010). When the group is infinite, the problem is still largely.

It turns out that the nature of singularities play a deep important role in this classification. Making use of the general and powerful approach proposed in the book [3] , a paper entitled Some exact asymptotics in the counting of walks in the quarter-plane has been submitted to AofA (International Conference on Analysis of Algorithms, Montreal, june 2012), in which a new approach is proposed to obtain some exact asymptotics for walks confined to the quarter plane.

Statistical physics and hydrodynamic limits

Participants : Guy Fayolle, Cyril Furtlehner.

Having in mind a global project concerning the analysis of complex systems, we first focus on the interplay between discrete and continuous description: in some cases, this recurrent question can be addressed quite rigorously via probabilistic methods.

To attack this class of problems, in touch with many applications domains (e.g. biology, telecommunications, transportation systems), we started from paradigmatic elements, namely the discrete curves subjected to stochastic deformations, as those mentioned for instance in  [39] . After convenient mappings, it appears that most models can be set in terms of interacting exclusion processes, the ultimate goal being to derive hydrodynamic limits for these systems after proper scalings. We extend the key ideas of [39] , where the basic ASEP system on the torus was the toy model. The usual sequence of empirical measures, converges in probability to a deterministic measure, which is the unique weak solution of a Cauchy problem.

The Gordian knot is the analysis of a family of specific partial differential operators in infinite dimension. Indeed, the values of functions at given points play here the role of usual variables, their number becoming infinite. The method presents some new theoretical features, involving promeasures (as introduced by Bourbaki), variational calculus, functional integration, and the construction of generalized measures. In [20] , we present a detailed analysis of the asep system on the torus $\mathbb{Z}/N\mathbb{Z}$. Then we claim that most of the arguments a priori work in higher dimensions (abc , multi-type exclusion processes, etc), leading to sytems of coupled partial differential equations of Burgers' type. In the course of the study, several fascinating multi-scale problems emerge quite naturally, bringing to light some connections with the so-called renormalization in theoretical physics.